#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5,M=2e6+5;
long long n,m,cc,t,a[M],b[M],dp[N][N],c[M],mx[N],sum,top,po[N];
__int128 qwq;
int main()
{
	freopen("festival.in","r",stdin);
	freopen("festival.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>cc>>t;
	while(t--)
	{
		cin>>n>>m;
		for(int i=1;i<n;++i)
			cin>>a[i];
		for(int i=1;i<=n;++i)
			c[i]=0;
		for(int i=1;i<=m;++i)
			cin>>b[i];
		if(n>3000&&m==1)
		{
			c[1]=a[1],c[n]=a[n-1];
			sum=a[1]+a[n-1];
			for(int i=2;i<n;++i)
				c[i]=min(a[i-1]-c[i-1],a[i]-c[i+1]),sum+=c[i];
			qwq=(__int128)b[1]*sum;
			top=0;
			while(qwq)
			{
				++top;
				po[top]=qwq%10;
				qwq/=10;
			}
			for(int i=top;i>=1;--i)
				cout<<po[i];
			cout<<'\n';
		}
		else{
			for(int i=1;i<=n-m+1;++i)
				for(int j=1;j<=m;++j)
					c[i+j-1]+=b[j];
			for(int j=0;j<=a[1];++j)      
				dp[1][j]=j*c[1],mx[j]=max(mx[j-1],dp[1][j]);
			a[n]=a[n-1];
			for(int i=2;i<=n;++i)
			{
				for(int j=0;j<=min(a[i-1],a[i]);++j)
					dp[i][j]=j*c[i]+mx[a[i-1]-j];
				for(int j=0;j<=a[i];++j)
					mx[j]=max(mx[j-1],dp[i][j]);
			}
			cout<<mx[a[n]]<<'\n';
			for(int i=1;i<=n;++i)
				for(int j=0;j<=a[i];++j)
					dp[i][j]=0;
		}
	}
	return 0;
}
